package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-14 00:05
 **/
public class LeetCode540 {

    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int m = l + r >> 1;
            //是偶数,满足nums[i] = nums[i + 1], 则l = m, 否则 r = m - 1;
            if (m % 2 == 0) {
                if (m + 1 < n && nums[m] == nums[m + 1]) {
                    l = m;
                } else {
                    r = m - 1;
                }
            } else {
                //是奇数的话,如果该数之前未插入单一元素,则nums[m] = nums[m - 1],则l = m,否则 r = m - 1;
                if (m - 1 >= 0 && nums[m] == nums[m - 1]) {
                    l = m;
                } else {
                    r = m - 1;
                }
            }
        }
        return l;
    }

    /*public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[n - 1];
    }*/

}
